//class Solution {
//public:
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (root == NULL || root == p || root == q)
//            return root;
//        TreeNode* left = lowestCommonAncestor(root->left, p, q);
//        TreeNode* right = lowestCommonAncestor(root->right, p, q);
//        if (left != NULL && right != NULL)
//            return root;
//        return left != NULL ? left : right;
//    }
//};




class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        queue<TreeNode*> q1, q2;
        q1.push(root->left), q2.push(root->right);
        while (!q1.empty() && !q2.empty())
        {
            TreeNode* val1 = q1.front(); q1.pop();
            TreeNode* val2 = q2.front(); q2.pop();

            if (val1 == nullptr && val2 == nullptr) continue;
            if (val1 == nullptr || val2 == nullptr) return false;
            if (val1->val != val2->val) return false;
            q1.push(val1->left);
            q2.push(val2->right);
            q1.push(val1->right);
            q2.push(val2->left);
        }
        return q1.empty() && q2.empty();
    }
};